#include "Tree.h"


template<typename Data> 
Node<Data>::Node()
{
	left = NULL;
	right = NULL;
}

template<typename Data>
Tree<Data>::Tree()
{
	root = NULL;
}

template<typename Data> 
Node<Data>* Tree<Data>::recursiveFind(Data value, Node<Data>* r)
{
	if(r == NULL)
		return NULL;
	else //root is not null
	{
		if(value == r->value)
			return r;
		else if(value > r->value)//greater is right
			return recursiveFind(value, r->right);
		else //lesser is left
			return recursiveFind(value, r->left);
	}
}

template<typename Data> 
Node<Data>* Tree<Data>::findParent(Data value, Node<Data>* r)
{
	if(r == NULL)
		return NULL;
	else //root is not null
	{
		if(value > r->value)//greater is right
		{
			//I must return the value
			if(r->right == NULL || r->right->value == value)
				return r;
			else
				return findParent(value, r->right);
		}
		else //lesser is left
		{
			//I must return the value
			if(r->left == NULL || r->left->value == value)
				return r;
			else
				return findParent(value, r->left);
		}
	}
}


template<typename Data> 
Node<Data>* Tree<Data>::find(Data value)
{
	return recursiveFind(value, root);
}

template<typename Data> 
void Tree<Data>::add(Data value)
{
	Node<Data>* r = findParent(value, root);
	if(r == NULL) //the root is null.
	{
		Node<Data>* newNode = 
			(Node<Data>*) Embeddable::embed_malloc(sizeof(Node<Data>));
		newNode->value = value;
		newNode->left = NULL;
		newNode->right = NULL;
		root = newNode;
	}
	else if(!(r->value == value)) //I need to add the node else do not add it.
	{
		if(r->right != NULL && r->right->value == value)
			return;
		else if(r->left != NULL && r->left->value == value) 
			return; //no need to add value in this case.
		Node<Data>* newNode = 
			(Node<Data>*) Embeddable::embed_malloc(sizeof(Node<Data>));
		newNode->value = value;
		newNode->left = NULL;
		newNode->right = NULL;
		if(value > r->value) //greater is right
			r->right = newNode;
		else //lesser is left.
			r->left = newNode;
	}
	
}

template<typename Data> 
void Tree<Data>::remove(Data value)
{
	Node<Data>* node = find(value);
	Node<Data>* parent = findParent(value, root);
	if(node == NULL)
		return;
	else
	{
		//get this nodes children first.
		Node<Data>* leftChild = node->left;
		Node<Data>* rightChild = node->right;
		//remove the node from its parent.
		if(parent->left == node)
			parent->left = NULL;
		else if(parent->right == node)
			parent->right = NULL;
		//before removing the node in question check the children
		if(leftChild != NULL) //find someone to adopt the child.
		{
			//find a parent to adopt this subtree.
			Node<Data>* newParent = findParent(leftChild->value,
							parent);
			if(leftChild->value > newParent->value
				&& newParent->right == NULL)
				newParent->right = leftChild;
			else
				newParent->left = leftChild;
			
		}

		if(rightChild != NULL) //find someone to adopt the child.
		{
			//find a parent to adopt this subtree.
			Node<Data>* newParent = findParent(rightChild->value,
							parent);
			if(rightChild->value > newParent->value
				&& newParent->right == NULL)
				newParent->right = leftChild;
			else
				newParent->left = leftChild;
			
		}
	}
}

template<typename Data> 
void Tree<Data>::deleteAll(Node<Data>* r)
{
	if(r!=NULL)
	{
		//delete left
		deleteAll(r->left);
		//delete right
		deleteAll(r->right);
		//delete the actual node now
		Embeddable::embed_free(r);
		r = NULL;
		return;
	}
}
template<typename Data> 
Tree<Data>::~Tree()
{
	deleteAll(root);
	root = NULL;
}


